package binaryTree;
//  CKG TODO 2023/4/1: 这道题目的关键就是找出所有　　可能进行交换的情况　　因为题目要求只能交换两个节点　　
//  CKG TODO 2023/4/1: 所有就不需要全局遍历　只需要找出所有可能交换的情况ｓ

//情况一：根节点与左孩子最大的节点进行交换
//情况二：根节点与右孩子最小的节点进行交换
//情况三：根节点左子树的俩个节点进行交换
//情况四：根节点的右子树的两个节点进行交换
//情况五：根节点的左子树一个节点与根节点右子树的一个节点交换

public class Class99 {

    public void recoverTree2(TreeNode root) {
        if (root == null) {
            return;
        }
        //寻找左子树中最大的节点
        TreeNode maxLeft = getMaxOfBST(root.left);
        //寻找右子树中最小的节点
        TreeNode minRight = getMinOfBST(root.right);

        if (minRight != null && maxLeft != null) {
            //左边的大于根节点，右边的小于根节点，对应情况 3，左右子树中的两个数字交换
            if ( maxLeft.val > root.val && minRight.val < root.val) {
                int temp = minRight.val;
                minRight.val = maxLeft.val;
                maxLeft.val = temp;
            }
        }

        if (maxLeft != null) {
            //左边最大的大于根节点，对应情况 1，根节点和左子树的某个数做了交换
            if (maxLeft.val > root.val) {
                int temp = maxLeft.val;
                maxLeft.val = root.val;
                root.val = temp;
            }
        }

        if (minRight != null) {
            //右边最小的小于根节点，对应情况 2，根节点和右子树的某个数做了交换
            if (minRight.val < root.val) {
                int temp = minRight.val;
                minRight.val = root.val;
                root.val = temp;
            }
        }
        //对应情况 4，左子树中的两个数进行了交换
        recoverTree2(root.left);
        //对应情况 5，右子树中的两个数进行了交换
        recoverTree2(root.right);

    }
    //寻找树中最小的节点
    private TreeNode getMinOfBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode minLeft = getMinOfBST(root.left);
        TreeNode minRight = getMinOfBST(root.right);
        TreeNode min = root;
        if (minLeft != null && min.val > minLeft.val) {
            min = minLeft;
        }
        if (minRight != null && min.val > minRight.val) {
            min = minRight;
        }
        return min;
    }

    //寻找树中最大的节点
    private TreeNode getMaxOfBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode maxLeft = getMaxOfBST(root.left);
        TreeNode maxRight = getMaxOfBST(root.right);
        TreeNode max = root;
        if (maxLeft != null && max.val < maxLeft.val) {
            max = maxLeft;
        }
        if (maxRight != null && max.val < maxRight.val) {
            max = maxRight;
        }
        return max;
    }

}
